/**
 * 
 * 斐波那契数列
 * 
 * 描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 
f
i
b
(
x
)
=
{
1
x
=
1
,
2
f
i
b
(
x
−
1
)
+
f
i
b
(
x
−
2
)
x
>
2
 
fib(x)={ 
1
fib(x−1)+fib(x−2)
​	
  
x=1,2
x>2
​	
  的数列
数据范围：
1
≤
n
≤
40
1≤n≤40
要求：空间复杂度 
O
(
1
)
O(1)，时间复杂度 
O
(
n
)
O(n) ，本题也有时间复杂度 
O
(
l
o
g
n
)
O(logn) 的解法

输入描述：

一个正整数n
返回值描述：

输出一个正整数。
 * 
 */
public class 斐波那契数列 {
    
    public static void main(String[] args) {
        
        System.out.println(Fibonacci(4));

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public static int Fibonacci (int n) {
        // write code here
        if(n<1) return 0;
        if(n == 1 || n ==2) return 1;

        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
